3700. Easy Dijkstra Problem

Determine the shortest path between the specified vertices in the graph given in the input data.

· Hint: You can use Dijkstra's algorithm.

· Hint 2: if you're a lazy C++ programmer, you can use set and cin/cout (with sync_with_stdio(0)) – it should suffice.

Input. First line contains the number of test cases. For each test case the number of vertices v and the number of edges are given. Then k lines follow, each containing the following numbers separated by a single space: a_i, b_i, c_i. It means that the graph being described contains an edge from a_i to b_i, with a weight of c_i. Below the graph description a line containing a pair of integers A, B is present. The goal is to find the shortest path from vertex A to vertex B. All numbers in the input data are integers in the range 0..10000.

Output. For each test case your program should output (in a separate line) the length of the shortest path from vertex A to vertex B. In case there is no such path, your program should output a single word "NO" (without quotes).

Sample input	Sample output
3 3 2 1 2 5 2 3 7 1 3 3 3 1 2 4 1 3 7 2 3 1 1 3 3 1 1 2 4 1 3	12 5 NO

РЕШЕНИЕ

алгоритм Дейкстры

Анализ алгоритма

В задаче следует реализовать алгоритм Дейкстры. Поскольку количество вершин и ребер в графе до 10000, то граф следует хранить в виде списка смежности. Граф является ориентированным.

Реализация алгоритма

#include <cstdio>

#include <cstring>

#include <vector>

#define MAX 10010

#define INF 2100000000

using namespace std;

int i, j, MinDist, n, Edges, source, dest;

int b, e, dist, w, tests;

struct road

{

int v, dist;

road(int vv, int dd) {v = vv; dist = dd;}

};

vector<vector<road> > m;

int used[MAX], d[MAX];

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&Edges);

m.assign(n+1,vector<road>());

memset(used,0,sizeof(used));

for(i = 0; i < Edges; i++)

{

scanf("%d %d %d",&b,&e,&dist);

m[b].push_back(road(e,dist));

}

scanf("%d %d",&source,&dest);

memset(d,0x3F,sizeof(d)); d[source] = 0;

for(i = 1; i < n; i++)

{

MinDist = INF / 2;

for(j = 1; j <= n; j++)

if (!used[j] && d[j] < MinDist) {MinDist = d[j]; w = j;}

for(j = 0; j < m[w].size(); j++)

{

road to = m[w][j];

if (!used[to.v]) d[to.v] = min(d[to.v], d[w] + to.dist);

}

used[w] = 1;

}

if (d[dest] == 0x3F3F3F3F) printf("NO\n");

else printf("%d\n",d[dest]);

}

return 0;

}

Реализация алгоритма - классы

#include <cstdio>

#include <vector>

#include <queue>

#define INF 0x3F3F3F3F

using namespace std;

class Edge

{

public:

int To, Len;

Edge(int To, int Len = 1) : To(To), Len(Len) {}

};

class Prior

{

public:

int Dist, Vertex;

Prior(int Dist, int Vertex) : Dist(Dist), Vertex(Vertex) {}

int operator< (const Prior &a) const

{

return Dist < a.Dist;

}

int operator> (const Prior &a) const

{

return Dist > a.Dist;

}

};

class Graph

{

public:

static const int INF2 = 0x3F3F3F3F;

int n;

vector<vector<Edge> > g;

Graph(int n = 1) : n(n)

{

g = vector<vector<Edge> >(n);

}

void AddEdge(int From, int To, int Len)

{

g[From].push_back(Edge(To,Len));

}

void Dijkstra(int Source, vector<int> &dist)

{

priority_queue<Prior, vector<Prior>, greater<Prior> > pq;

//(distance,node)

pq.push(Prior(0,Source)); dist[Source] = 0;

while(!pq.empty())

{

int v = pq.top().Vertex;

int d = pq.top().Dist; pq.pop();

if (d > dist[v]) continue;

for(int i = 0; i < g[v].size(); i++)

{

int to = g[v][i].To ; // v -> to

int Len = g[v][i].Len;

if (dist[to] > dist[v] + Len)

{

dist[to] = dist[v] + Len;

pq.push(Prior(dist[to],to));

}

}

}

}

};

int i, n, tests, From, To, Len;

int Source, Dest, Edges;

Graph *g;

vector<int> dist;

int main(void)

{

scanf("%d",&tests);

while(tests--)

{

scanf("%d %d",&n,&Edges);

g = new Graph(n+1);

dist = vector<int>(n+1,INF);

for(i = 0; i < Edges; i++)

{

scanf("%d %d %d",&From,&To,&Len);

g->AddEdge(From,To,Len);

}

scanf("%d %d",&Source,&Dest);

g->Dijkstra(Source,dist);

if (dist[Dest] == INF) printf("NO\n");

else printf("%d\n",dist[Dest]);

}

return 0;

}